DSC 40B – Theoretical Foundations of Data Science II

Problems tagged with "recurrence relations"

Problem #011

Tags: recurrence relations

State (but do not solve) the recurrence describing the run time of the following code, assuming that the input, arr, is a list of size \(n\).


def foo(arr, stop=None):
    if stop is None:
        stop = len(arr) - 1

    if stop < 0:
        return 1

    last = arr[stop]
    return last * foo(arr, stop - 1)
Solution

\(T(n) = T(n-1) + \Theta(1)\)

Problem #012

Tags: recurrence relations

What is the solution of the below recurrence? State your answer using asymptotic notation as a function of \(n\).

\[ T(n) = \begin{cases} 5 T(n/5) + \Theta(n),& n > 1\\ 1,& n = 1 \end{cases}\]
Solution

\(\Theta(n \log n)\)

Problem #028

Tags: recurrence relations

State (but do not solve) the recurrence describing the runtime of the following function.


def foo(n):
    if n < 10:
        print("Hello world.")
        return

    for i in range(n):
        print(i)

    for i in range(6):
        foo(n//3)
Solution

\(T(n) = 6 T(n/3) + \Theta(n)\).

Problem #044

Tags: recurrence relations

Solve the below recurrence, stating the solution in asymptotic notation. Show your work.

\[ T(n) = \begin{cases} 2 T(n/4) + \Theta(n) & n > 1 \\ c & n = 1 \end{cases}\]
Solution

\(\Theta(n)\).

We'll unroll several times:

\[\begin{aligned} T(n) &= 2 T(n/4) + n \\ &= 4 T(n/16) + \frac{n}{2} + n \\ &= 8 T(n/64) + \frac{n}{4} + \frac{n}{2} + n \\ \end{aligned}\]

The pattern seems to be that on the \(k\)th unroll:

\[ T(n) = 2^k T\left(\frac{n}{4^k}\right)+ n \left( 1 + \frac12 + \frac14 + \ldots + \frac{1}{2^{k-1}}\right)\]

The base case is reached when \(k = \log_4 n\). Plugging this back in, we find:

\[ T(n) = 2^{\log_4 n} T(1) + n \left(1 + \frac12 + \frac 14 + \ldots + \frac{1}{2^{\log_4 n - 1}}\right)\]

If you reached this point, you got most of the credit. If you're unsure of what to do with \(2^{\log_4 n}\), there are a couple of ways foward.

The first (and easiest) way is to realize that \(2^{\log_4 n}\) is smaller than \(2^{\log_2 n} = n\), so \(2^{\log_4 n} = O(n)\). Similarly, we've seen the summation of \(1 + 1/2 + 1/4 + \ldots\) several times -- this is a geometric sum, and converges to 2 when there are infinitely many terms. There are a finite number of terms here, so the sum is \(< 2\). Altogether, we have:

\[ T(n) = O(n) T(1) + n \Theta(1) = \Theta(n) \]

The second approach is to remember log properties to simplify \(2^{\log_4 n}\) to \(\sqrt{n}\). This can be seen by using the ``change of base'' formula:

\[\log_b x = \frac{\log_a x}{\log_a b}. \]

In this case:

\[\log_4 n = \frac{\log_2 n}{\log_2 4} = \frac{\log_2 n}{2}\]

And therefore \(2^{\log_4 n} = 2^{(\log_2 n) / 2} = \left(2^{\log_2 n}\right)^{1/2} = n^{1/2} = \sqrt n\). This shows that the first term in the recurrence is \(\Theta(\sqrt n)\). The second term is still \(\Theta(n)\), so the solution is \(\Theta(n)\).

Problem #056

Tags: recurrence relations

State (but do not solve) the recurrence describing the runtime of the following function.


def foo(n):
    if n < 1:
        return 0

    for i in range(n**2):
        print("here")

    foo(n/2)
Solution

\( T(n) = \begin{cases} \Theta(1), & n = 1\\ T(n/2) + \Theta(n^2)% , & n > 1 \end{cases}\)

Problem #068

Tags: recurrence relations, mergesort

Consider the modification of mergesort shown below, where one of the recursive calls has been replaced by an in-place version of selection_sort. Recall that selection_sort takes \(\Theta(n^2)\) time.


def kinda_mergesort(arr):
    """Sort array in-place."""
    if len(arr) > 1:
        middle = math.floor(len(arr) / 2)
        left = arr[:middle]
        right = arr[middle:]
        mergesort(left)
        selection_sort(right)
        merge(left, right, arr)

What is the time complexity of kinda_mergesort?

Solution

\(\Theta(n^2)\)

Problem #071

Tags: recurrence relations

Solve the below recurrence, stating the solution in asymptotic notation. Show your work.

\[ T(n) = \begin{cases} T(n/2) + \Theta(n) & n > 1 \\ \Theta(1) & n = 1 \end{cases}\]
Solution

\(\Theta(n)\).

Unrolling several times, we find:

\[ T(n) = T(n/2) + n \\ = T(n/4) + \frac{n}{2} + n \\ = T(n/8) + \frac{n}{4} + \frac{n}{2} + n \\\]

On the \(k\)th unroll, we'll get:

\[ T(n) = T(n/2^k) + \left[ n + \frac{n}{2} + \frac{n}{4} + \ldots + \frac{n}{2^{k-1}}\right]\]

It will take \(\log_2 n\) unrolls to each the base case. Substituting this for \(k\), we get:

\[\begin{aligned} T(n) &= T(n/2^{\log_2 n}) + \left[ n + \frac{n}{2} + \frac{n}{4} + \ldots + \frac{n}{2^{(\log_2 n)-1}} \right] \\ &= T(1) + n\left[ 1 + \frac{1}{2} + \frac{1}{4} + \ldots + \frac{1}{2^{(\log_2 n)-1}} \right] & = T(1) + c n\\ & = \Theta(1) + c n\\ &= \Theta(n) \end{aligned}\]

Problem #082

Tags: recurrence relations

Solve the recurrence below, stating the solution in asymptotic notation. Show your work.

\[ T(n) = \begin{cases} 2 T(n/4) + \Theta(n),& n > 1\\ 1,& n = 1 \end{cases}\]
Solution

\(\Theta(n)\)

Problem #085

Tags: recurrence relations

State (but do not solve) the recurrence describing the run time of the following code, assuming that the input, arr, is a list of size \(n\).


def foo(arr, stop=None):
    if stop is None:
        stop = len(arr) - 1

    if stop < 0:
        return 1

    last = arr[stop]
    return last * foo(arr, stop - 1)
Solution

\(T(n) = T(n-1) + \Theta(1)\)